package JZ_Offer.dataStructure.list;

import base.ListNode;

/**
 * 反转链表
 * <p>
 * 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
 * <p>
 * 数据范围： n\leq1000n≤1000
 * 要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
 * <p>
 * 如当输入链表{1,2,3}时，
 * 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
 *
 * @Author piper
 * @Date 2019/12/4 11:10 上午
 */
public class JZ24_反转链表 {

    /**
     * 想象三个指针 当前节点、前驱、后继
     * 将当前节点后继取出
     * 将当前节点next指针指向前驱节点
     * 将当前节点赋值给前驱
     * 将后继节点赋值给当前节点 以便下次循环
     */
    private static ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            // 保存下一个节点
            next = head.next;
            // 反转当前节点指向为前驱
            head.next = pre;
            // 当前节点赋值给前驱
            pre = head;
            // 下一个节点赋值给当前节点
            head = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        ListNode listNode = ReverseList(a);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
